Simulated evolution and simulated annealing algorithms for solving multi-objective open shortest path first weight setting problem

摘要

Optimal utilization of resources in present-day communication networks is a challenging task. Rout-ing plays an important role in achieving optimal re-source utilization. The open shortest path rst (OSPF)routing protocol is widely used for routing packets froma source node to a destination node. This protocol as-signs weights (or costs) to the links of a network. Theseweights are used to determine the shortest path be tween all sources to all destination nodes. Assignmentof these weights to the links is classi ed as an NP-hardproblem. This paper formulates the OSPF weight set-ting problem as a multi-objective optimization prob-lem, with maximum utilization, number of congestedlinks, and number of unused links as the optimizationobjectives. Since the objectives are conicting in na-ture, an e cient approach is needed to balance thetrade-o between these objectives. Fuzzy logic has beenshown to e ciently solve multi-objective optimizationproblems. A fuzzy cost function for the OSPF weightsetting problem is developed in this paper based on theUni ed And-OR (UAO) operator. Two iterative heuris-tics, namely, simulated annealing (SA) and simulatedevolution (SimE) have been implemented to solve themulti-objective OSPF weight setting problem using afuzzy cost function. Results are compared with thatfound using other cost functions proposed in the literature [1]. Results suggest that, overall, the fuzzy costfunction performs better than existing cost functions,with respect to both SA and SimE. Furthermore, SimEshows superior performance compared to SA. In addi-tion, a comparison of SimE with NSGA-II shows that,overall, SimE demonstrates slightly better performancein terms of quality of solutions.-